package com.zx._12_算法;

import com.zx._12_算法.数据结构.stack.Stack;
import java.util.LinkedList;

public class TreeNode {

    public static final TreeNode root = new TreeNode(1);

    static {
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        TreeNode node9 = new TreeNode(9);
        TreeNode node10 = new TreeNode(10);
        TreeNode node11 = new TreeNode(11);
        TreeNode node12 = new TreeNode(12);
        TreeNode node13 = new TreeNode(13);
        TreeNode node14 = new TreeNode(14);
        TreeNode node15 = new TreeNode(15);

        root.left = node2;
        root.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.left = node6;
        node3.right = node7;

        node4.left = node8;
        node4.right = node9;

        node5.left = node10;
        node5.right = node11;

        node6.left = node12;
        node6.right = node13;

        node7.left = node14;
        node7.right = node15;


    }

    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }

//	static {
//		TreeNode node2 = new TreeNode(2); 
//		TreeNode node3 = new TreeNode(3);
//		TreeNode node4 = new TreeNode(4);
//		TreeNode node5 = new TreeNode(5);
//		TreeNode node6 = new TreeNode(6);
//		TreeNode node7 = new TreeNode(7);
//		
//		root.left = node2;
//		root.right = node3;
//		 
//		node2.left = node4;
//		node2.right = node5; 
//		
//		node3.left = node6;
//		node3.right = node7; 
//	}

    public TreeNode() {
    }

    // 前序遍历-中左右
    public static void qian(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.println(root.val);
        qian(root.left);
        qian(root.right);
    }

    // 逐层遍历
    public static void loop() {
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode treeNode = TreeNode.root;
        queue.add(treeNode);

        int nowLen = 0;
        while ((nowLen = queue.size()) != 0) {
            String print = "";
            for (int i = 0; i < nowLen; i++) {
                TreeNode pop = queue.pop();
                print += pop.val + "\t";
                if (pop.left != null) {
                    queue.add(pop.left);
                }
                if (pop.right != null) {
                    queue.add(pop.right);
                }
            }
            System.out.println(print);
        }
    }

    public static void main(String[] args) {
        loop();
    }

    /**
     * @param exp A(B(D,E(G,)),C(,F))#
     *  如何用广义表来表达二叉树呢，以广义表 A(B(D,E(G,)),C(,F))# 为例，算法如下
     *  1. 广义表的表名放在表前，表示树的根节点，括号中的是根的左右子树
     *  2. 每个节点的左右子树用逗号隔开，如果有仅有右子树没有左子树，逗号不省略
     *  3. 整个广义表的最后加上特殊符号#表示输入结束
     *  A(
     *  B(
     *  D,
     *  E(
     *  G,
     *  )
     *  ),
     *  C(,F)
     *  )#
     * @Title: 采用广义表表示的建立二叉树方法
     * @date: 2019年8月31日下午8:53:29
     * @author: zhangxue
     */
    public static TreeNode buildTree(String exp) {
        TreeNode root = null;// 生成一个新的root

        Stack<TreeNode> stack = new Stack();

        char[] chars = exp.toCharArray();

        boolean isLeft = true;

        TreeNode node = null;
        for (char c : chars) {
            if (c == '(') {
                stack.push(node);
                isLeft = true;
            } else if (c == ',') {
                isLeft = false;
            } else if (c == ')') {
                stack.pop();
            } else if (c == '#') {

            } else {
                node = new TreeNode();
                node.val = Integer.parseInt(String.valueOf(c));
                if (root == null) {
                    root = node;
                } else if (isLeft) {
                    // 左子树
                    TreeNode top = stack.top();
                    top.left = node;
                } else {
                    // 右子树
                    TreeNode top = stack.top();
                    top.right = node;
                }

            }
        }
        return root;
    }

    public static int size(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = size(node.left);
        int right = size(node.right);
        return 1 + left + right;
    }

    /**
     * 返回树的高度
     * 叶节点的高度为1，非叶节点的高度是它子女节点高度的最大值加1
     *
     * @date: 2019年9月4日下午9:47:28
     * @author: zhangxue
     */
    public static int height(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftH = height(node.left);
        int rightH = height(node.right);
        // 当前是叶子节点
        if (leftH == 0 && rightH == 0) {
            return 1;
        } else if (leftH > rightH) {
            return leftH + 1;
        } else {
            return rightH + 1;
        }
    }

    public static TreeNode find(TreeNode node, int data) {
        if (node == null) {
            return null;
        }

        if (node.val == data) {
            return node;
        }

        TreeNode left = find(node.left, data);
        if (left != null) {
            return left;
        }

        TreeNode right = find(node.right, data);
        if (right != null) {
            return right;
        }

        return null;
    }

    @Override
    public String toString() {
        return val +
                (
                        (left == null && right == null) ?
                                "" : "("
                                + (left == null ? "" : left.toString())
                                + ", "
                                + (right == null ? "" : right.toString())
                                + ")"
                )
                ;
    }

    public String toStr2() {
        return val
                + "("
                + (left == null ? "" : left.toStr2())
                + ", "
                + (right == null ? "" : right.toStr2())
                + ")"
                ;
    }

    public void print() {
        System.out.println(this.toString());
        System.out.println(this.toStr2());
    }
}
